package com.company.KKMP;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}8:19
 */
public class KMP {
    public static void prefix_table(char[] pattern, int[] prefix, int n){
        prefix[0] = 0;
        int len = 0;
        int i = 1;
        while (i < n){
            if (pattern[i] == pattern[len]){
                len++;
                prefix[i] = len;
                i++;
            }else {
                if (len > 0) {
                    len = prefix[len - 1];//斜着来一手映射
                }else {
                    prefix[i] = len;
                    i++;
                }
            }
        }
    }

    public static void move_prefix_table(int prefix[], int n){
        for (int i = n -1; i > 0;i--){
            prefix[i] = prefix[i-1];
        }
        prefix[0] = -1;
    }

    public static void kmp_search(char[] text,char[] pattern,int[] prefix){
        int n = pattern.length;
        prefix_table(pattern,prefix,n);
        move_prefix_table(prefix,n);
        int m = text.length;
        //下面进行移动
        int i = 0;
        int j = 0;
        while (i < m){
            if (j == n - 1 && text[i] == pattern[j]){
                System.out.println("Found over"+ (i - j));
                j = prefix[j];
            }
            if (text[i] == text[m]){
                i++;
                j++;
            }else {//通过前缀表移动
                j = prefix[j];
                if (j == -1){
                    i++;
                    j++;
                }
            }
        }
    }

    public static void main(String[] args) {
        char[] pattern = "ABABCABAA".toCharArray();
        int[] prefix = new int[9];
        char[] text = "ABABABCABAABABABAB".toCharArray();
        kmp_search(text,pattern,prefix);
//        int n = 9;
//        prefix_table(pattern,prefix,n);
//        move_prefix_table(prefix,n);
//        for (int i = 0; i < n; i++){
//            System.out.println(prefix[i]);
//        }


    }
}
